CS224n Lecture 4 Dependency Parsing
1. Two views of linguistic structure
两个语言结构观点: Constituency = 句子结构 = 无上下文语法 context-free grammars (CFG)
context-free grammars
句子结构组织单词成嵌套成分
句子及各个组织单词成嵌套成分
- 能用CFG规则来表示语法
- 起步单元:单词被赋予一个类别 (part of speech = pos)
- 单词可以组成不同类别的短语
- 短语可以递归第组合成更大的短语
其中,
Det
指的是 Determiner,在语言学中的含义为 限定词NP
指的是 Noun Phrase ,在语言学中的含义为 名词短语VP
指的是 Verb Phrase ,在语言学中的含义为 动词短语P
指的是 Preposition ,在语言学中的含义为 介词
PP
指的是 Prepositional Phrase ,在语言学中的含义为 介词短语- NP→Det N
- NP→Det (Adj) N
- NP→Det (Adj) N PP
- PP→P NP
- VP→V P
- 中文中,介词短语会出现在动词之前
Dependency Parsing
依存分析是一种在计算语言学中占主导地位的观点。
依存结构表示哪些词依赖(修饰或其参数)哪些其他词。
look是整个句子的root, 而look又依赖于crate。
- in, the, large都是crate依赖
- in the kitchen都是crate的修饰
- in, the都是kitchen的依赖,同理分析by the door
为什么我们要句子结构?
- 我们需要理解句子结构,为了能正确解释语言。
- 人类交流复杂想法通过将单词组合在一起合成更大的单元来传达复杂意思。
- 我们需要知道什么联系什么
Prepositional phrase attachment ambiguity
介词短语依存歧义
- 警察用刀杀了那个男子
cops
是kill
的subject
(subject 指 主语)man
是kill
的object
(object 指 宾语)knife
是kill
的modifier
(modifier 指 修饰符)- 警察杀了那个有刀的男子
knife
是man
的modifier
(名词修饰符,简称为nmod
)
from space
这一介词短语修饰的是前面的动词count
还是名词whales
?
PP attachment ambiguities multiply
- 关键分析决策是我们怎样”依存“不同成分
- 名词短语,形容词或分词、不定式和协调等。
- 上述句子中有四个介词短语
board
是approved
的 主语,acquisition
是approved
的谓语by Royal Trustco Ltd.
是修饰acquisition
的,即董事会批准了这家公司的收购of Toronto
可以修饰approved, acquisition, Royal Trustco Ltd.
之一,经过分析可以得知是修饰Royal Trustco Ltd.
即表示这家公司的位置for $27 a share
修饰acquisition
at its monthly meeting
修饰approved
,即表示批准的时间地点面对这样复杂的句子结构,我们需要考虑 指数级 的可能结构,这个序列被称为 Catalan numbers
Catalan numbers :
- 一个指数增长的序列,出现在许多类似树的环境中
- 例如,一个 n+2 边的多边形可能的三角剖分的数量
- 出现在概率图形模型的三角剖分中(CS228)
Coordination scope ambiguity
协调范围歧义
- 一个人:[[Shuttle veteran and longtime NASA executive] Fred Gregory] appointed to board(航天飞机老兵、长期担任美国宇航局主管弗雷德-格雷戈里被任命为董事会成员)
- 两个人:[Shuttle veteran] and [longtime NASA executive Fred Gregory] appointed to board(航天飞机老兵和长期担任美国宇航局主管弗雷德-格雷戈里被任命为董事会成员)
Doctor: No heart, cognitive issues.
Adjectival Modifier Ambiguity
形容词修饰歧义
例句:Students get first hand job experience
first hand
表示 第一手的,直接的,即学生获得了直接的工作经验
first
是
hand的形容词修饰语
- first 修饰 experience, hand 修饰 job !
Verb Phrase (VP) attachment ambiguity
动词依存歧义
例句:Mutilated body washes up on Rio beach to be used for Olympic beach volleyball.
to be used for Olympic beach volleyball
是 动词短语 (VP)- 修饰的是
body
还是beach
Dependency paths identify semantic relations – e.g., for protein interaction
依赖路径识别语义关系
2. Dependency Grammar and Dependency Structure
依存语法假定句法结构由词汇项之间的关系构成,通常是二元不对称关系(“箭头”), 称为依赖关系。
Dependency Structure有两种表现形式:
- 一种是直接在句子上标出依存关系箭头及语法关系
- 另一种是将其做成树状机构(Dependency Tree Graph)
- 箭头通常标记(type)为语法关系的名称(主题、介词对象、apposition等)。
- 依赖关系标签的系统,例如 universal dependency 通用依赖
- 箭头连接头部( head )和一个依赖(修饰词,下级,下属)
- A →依赖于 A 的事情
- 通常,依赖关系形成一棵树(单头 无环 连接图)
Dependency Grammar/Parsing History
- 依赖结构的概念可以追溯到很久以前
- Pāṇini的语法(公元前5世纪)
- 一千年 阿拉伯语的语法的基本方法
- 选区/上下文无关文法是一个新奇的发明
- 20世纪发明(R.S.Wells,1947; then Chomsky)
- 现代依赖工作经常源于 L. Tesnière(1959)
- 是20世纪“东方”的主导方法(俄罗斯,中国,…)
- 有利于更自由的语序语言
- NLP中最早类型的解析器在美国
- David Hays 是美国计算语言学的创始人之一,他很早就(第一个)构建了依赖解析器(Hays 1962)。
Dependency Grammar and Dependency Structure 表示方法
- 人们对箭头指向的方式不一致:有些人把箭头朝一个方向画;有人是反过来的
- Tesnière 从头开始指向依赖,本课使用此种方式
- 通常添加一个伪造“ROOT”指向整个句子的头部,这样每个单词都精确地依赖于另一个节点
注:从头指向依赖,加上个ROOT
The rise of annotated data: Universal Dependencies treebanks
标注数据的崛起:全局依存树库
Universal Dependencies:我们想要拥有一个统一的、并行的依赖描述,可用于任何人类语言
- 从前手工编写语法然后训练得到可以解析句子的解析器
- 用一条规则捕捉很多东西真的很有效率,但是事实证明这在实践中不是一个好主意
- 语法规则符号越来越复杂,并且没有共享和重用人类所做的工作
- 句子结构上的treebanks 支持结构更有效
The rise of annotated data
从一开始,构建 treebank 似乎比构建语法慢得多,也没有那么有用
但是 treebank 给我们提供了许多东西
- 劳动力的可重用性
- 许多解析器、词性标记器等可以构建在它之上
- 语言学的宝贵资源
- 广泛的覆盖面,而不仅仅是一些直觉
- 频率和分布信息
- 一种评估系统的方法
Dependency Conditioning Preferences
依存条件偏好
关于依存分析的信息来源是什么?
- Bilexical affinities (两个单词间的密切关系)
- [discussion →→ issues] 是看上去有道理的
- Dependency distance 依赖距离
- 主要是与相邻词
- Intervening material 介于中间的物质
- 依赖很少跨越介于中间的动词或标点符号
- Valency of heads 头部的配价
- 对于头部,多少依赖在哪边是普遍的?
Dependency Parsing
依存分析
- 通过为每个单词选择它所依赖的其他单词(包括根)来解析一个句子
- 通常有一些限制
- 只有一个单词是依赖于根的
- 不存在循环 A→B, A→B,
- 这使得依赖项成为树
- 最后一个问题是箭头是否可以交叉(非投影的 non-projective)
- 没有交叉的就是non-projectice
Projectivity
- 定义:当单词按线性顺序排列时,没有交叉的依赖弧,所有的弧都在单词的上方
- 与CFG树并行的依赖关系必须是投影的
- 通过将每个类别的一个子类别作为头来形成依赖关系
- 但是依赖理论通常允许非投射结构来解释移位的成分
- 如果没有这些非投射依赖关系,就不可能很容易获得某些结构的语义
Methods of Dependency Parsing
- Dynamic programming
- Eisner(1996)提出了一种复杂度为
的精巧算法,它生成头部位于末尾而不是中间的解析项 - Graph algorithms
- 为一个句子创建一个最小生成树
- McDonald et al.’s (2005) MSTParser 使用ML分类器独立地对依赖项进行评分(他使用MIRA进行在线学习,但它也可以是其他东西)
- Constraint Satisfaction
- 去掉不满足硬约束的边 Karlsson(1990), etc.
- “Transition-based parsing” or “deterministic dependency parsing“
- 良好的机器学习分类器 MaltParser(Nivreet al. 2008) 指导下的依存贪婪选择。已证明非常有效。
3. Greedy transition-based parsing [Nivre 2003]
基于贪婪转换解析
这部分要求要有数据结构和算法基础。
Transition-based Dependency Parsing 可以看做是state machine,对于一个序列
其中,
是S中若干个 组成的stack 是S中若干个 组成的buffer,将其看作一个队列,队列模拟的是人眼的阅读顺序,人眼从左到右阅读,系统也从左往右读入单词,未读入的单词就构成一个队列,队列的出口在左边。初始状态下队列就是整个句子,且顺序不变。- A是依存的arc构成的集合,如
,其中r是两个词之间的依存关系
初始化状态的时候,
只包含ROOT , 包含所有单词 , A是空集 .
最终状态,
包含ROOT和所有词, 清空,A包含所有依存arc,A就是我们需要的依存关系。
状态转移有三种方式:
- SHFIT: 从buffer移除第一个词,并将其送入栈的顶部(前提:buffer为空)
- LEFT-ARC: 将
加入边的集合 A ,其中 是stack上的次顶层的词, 是stack上的最顶层的词;然后再将 从栈中移除。(前提条件:栈至少包含两个词,且 不能是ROOT) - RIGHT_ARC:将
加入边的集合 A ,其中 是stack上的次顶层的词, 是stack上的最顶层的词; 然后再将 从栈中移除。(前提条件:栈至少包含两个词)
数学表示,(这样就可以理解整个过程就是上图意思)
还可以看看这里面的详细例子 举例说明
MaltParser [Nivreand Hall 2005]
- 我们需要解释如何选择下一步行动
- Answer:标准回答,机器学习
- 每个动作都由一个有判别分类器(例如softmax classifier)对每个合法的动作进行预测
- 最多三种无类型的选择,当带有类型时,最多 |R|×2+1种
- Features:栈顶单词,POS;buffer中的第一个单词,POS;等等
- (在最简单的形式中是)没有搜索的
- 但是,如果你愿意,你可以有效地执行一个 Beam search 束搜索(虽然速度较慢,但效果更好):你可以在每个时间步骤中保留 k个好的解析前缀
- 模型精度是略低于最新的依存解析,但是
- 它提供了非常快的线性时间解析,性能非常好
Conventional Feature Representation
传统特征表示
栈和队列中单词、词性、依存标签的组合的特征函数,一个超长的稀疏01向量。
Evaluation of Dependency Parsing: (labeled) dependency accuracy
依存解析的估计:标签的依存准确性
其中,UAS (unlabeled attachment score) 指 无标签依存正确率 ,LAS (labeled attachment score) 指 有标签依存正确率
一个是LAS(labeled attachment score)即只有arc的箭头方向以及语法关系均正确时才算正确,以及UAS(unlabeled attachment score)即只要arc的箭头方向正确即可。
例子中,
- 只看箭头方向,即Gold和Parsed中数字相同有4个,4/5,即80%
- 看箭头和解析后的标签只有2个,即2/5=40%
Handling non-projectivity
- 我们提出的弧标准算法只构建投影依赖树
- 可能指向头的方向
- 在非投影弧上宣告失败
- 只具有投影表示时使用依赖形式
- CFG只允许投影结构;改进扰乱头
- 使用投影依赖项解析算法的后处理器来识别和解析非投影链接
- 添加额外的转换,至少可以对大多数非投影结构建模(添加一个额外的交换转换,冒泡排序)
- 转移到不使用或不需要对投射性进行任何约束的解析机制(例如,基于图的MSTParser)
4. Why train a neural dependency parser? Indicator Features Revisited
为什么训练神经依存解析?重提指示符特征
传统特征表示稀疏、不完全、计算代价大(SVM之类的线性分类器本身是很快的,而传统parser的95%时间都花在拼装查询特征上了)。
A neural dependency parser [Chen and Manning 2014]
- 斯坦福依存英语解析
- 未便签依存分数UAS = head
- 标签依存分数LAS = head and label
相较于传统的graph-based方法,花了这么多功夫得到的只是0.1%的LAS提升。
Distributed Representations
分布表示
- 我们将每个单词表示为一个d维稠密向量(如词向量)
- 相似的单词应该有相近的向量
- 同时,part-of-speech tags词性标签(POS)和 dependency labels 依存标签也表示为d维向量
- 较小的离散集也表现出许多语义上的相似性。
- NNS(复数名词)应该接近NN(单数名词)
- num(数值修饰语)应该接近amod(形容词修饰语)。
对于Neural Dependency Parser,其输入特征通常包含三种
- stack和buffer中的单词及其dependent word
- 单词的part-of-speech tag
- 描述语法关系的arc label
Extracting Tokens and then vector representations from configuration
提取令牌和从配置中获得向量表示
将上图中的单词、词性标注和依存标签转换为词向量,并将它们联结起来。
Model Architecture
具体来说,将嵌入矩阵
网络结构由一个输入层、一个隐含层Relu、一个softmax输出层组成,使用交叉熵损失函数。
Dependency parsing for sentence structure
神经网络能准确决定句子结构,增加解释性。
Chen and Manning (2014) was the first simple, successful neural dependency parser
然后稠密表示,让其在准确性和速度上优于其它贪婪解析器。
Further developments in transition-based neural dependency parsing
这项工作由其他人进一步开发和改进,特别是在谷歌
- 更大、更深的网络中,具有更好调优的超参数
- Beam Search 更多的探索动作序列的可能性,而不是只考虑当前的最优
全局、条件随机场(CRF)的推理出决策序列
Graph-based dependency parsers
为每条边的每一个可能的依赖关系计算一个分数
- 然后将每个单词的边缘添加到其得分最高的候选头部
- 并对其它每个单词重复相同的操作
A Neural graph-based dependency parser
[ Dozat and Manning 2017; Dozat, Qi, and Manning 2017 ]
- 在神经模型中为基于图的依赖分析注入活力
- 为神经依赖分析设计一个双仿射评分模型
- 也使用神经序列模型,我们将在下周讨论
- 非常棒的结果
- 但是比简单的基于神经传递的解析器要慢
- 在一个长度为 n 的句子中可能有
个依赖项
参考
[1] 05 Linguistic Structure Dependency Parsing
[2] 2019年CS224N课程笔记-Lecture 5: Linguistic Structure: Dependency Parsing
[3] CS224N笔记(五):Dependency Parsing
[4] CS224n 2019 Winter 笔记(三):句子依存分析(Dependency Parsing)
[6] 依存句法分析 部分代码及分析